予測キャッシング型コンテンツ配信ネットワーク

专利摘要:
様々な例示的実施形態において、容量の制約があるネットワーク内でコンテンツを配信する方法は、最適なサービス品質の達成およびサービスセッション容量の最大化のために機能する分散されたコンテンツ記憶ノードを使用する。本方法は、ユニキャスト、ブロードキャスト、交換ブロードキャストおよびマルチキャストモードのネットワークで機能し、需要のピークが増加しない時間中および形態において、分散されたコンテンツ記憶装置に有用性の最も高いアイテムをダウンロードまたは記憶するために、特定のコンテンツアイテムの有用性の予測を利用する。こうした有用性予測は、例えば、潜在的ユーザの数、使用の可能性およびサービスプロバイダにとっての価値に基づいてよい。本方法は、特定のコンテンツアイテムの最良のソースを、どのノードが当該コンテンツを保持しているか、またネットワーク制約の性質に基づき特定するため、ネットワークノード間のシグナルを使用する。
公开号:JP2011511338A
申请号:JP2010540212
申请日:2008-12-22
公开日:2011-04-07
发明作者:シーゲル，ジヨナサン
申请人:アルカテル−ルーセント；
IPC主号:G06F12-00

专利说明:

[0001] 本発明は一般に、コンテンツ配信ネットワークの１つまたは複数のノードにおける情報のキャッシングまたは一時的記憶に関する。]
背景技術

[0002] ブロードバンドインターネットが拡大し続ける中、マルチメディアコンテンツのリアルタイム配信を求めるユーザの数が絶えず増大している。コンテンツ配信ネットワークはこのニーズに対し、コンテンツアイテムをキャッシュできるネットワーク化されたコンピュータまたはノードのシステムを介して、エンドユーザにデジタルコンテンツを配信することによって対応している。コンテンツ配信ネットワークは、地理的に分散した記憶装置を利用することで、高品質の大量のコンテンツへのアクセスをユーザに提供する。]
[0003] 一般に、コンテンツの配信のために最適化されたネットワークを構築する理由が２つある。第一の目的は、帯域幅の拡大ならびに待機時間およびジッタの低減を通じてユーザ体験の質を向上させることである。第二の目的は、ネットワークサービスの収益性を最適化することである。]
[0004] 一般に、ネットワークサービスの収益性は、平均的な利用度に影響され、コストは、ピークのトラフィック負荷に対応する大きさの設定済みネットワーク容量に影響される。コンテンツ需要が利用可能なネットワーク容量に近づくと、サービスプロバイダはサービスセッションをさらに配信することはできず、その結果、収益とサービスの質が低下する。また、このサービスの質低下により、サービス価格が下がることや、高い費用をかけてネットワーク容量を拡大する必要が生じることもある。]
[0005] ネットワークのコストを下げる一般的な技法は、トラフィック需要をピーク外時間に移行させてネットワークの拡大を延期し、ネットワークの輻輳を避けることである。記憶装置を組み込んでいるネットワークは、ピークをなくすために需要プロファイルを平滑化することができる。これらのネットワークは、コンテンツ配信ネットワークの実装コストを最小限に抑えつつ、サービス容量の拡大を実現することができる。]
[0006] コンテンツ記憶の階層はしっかりと確立されている。階層システムでは、ユーザが映像や音声などの１つのマルチメディアコンテンツを要求したとき、コンテンツ配信ネットワークは、ネットワークの近接性の点で最も近いサーバを選択することによって効率性を最大化する。例えば、コンテンツ配信ネットワークは、要求側ノードとサーバノードとの間のホップ数またはネットワーク遅延時間の最小化を試みることができる。一方、ユーザが要求するコンテンツが、要求側ノードに極めて接近した場所にあるサーバノードで入手できない場合、コンテンツ配信ネットワークの非効率性が高まることがある。こうした状況では、サーバノードは別のノードからコンテンツを取り出さなければならず、その結果、コンテンツ配信ネットワーク全体のトラフィック需要が増加する。]
[0007] 現在の多くのコンテンツ配信ネットワークは、エンドユーザパフォーマンスの向上という目標を達成しているが、使用されていないコンテンツを複製し配信することや、かかるコンテンツをピーク時間に配信することによって、ネットワークサービスプロバイダに対するコストを増大させる場合もある。現在のコンテンツ配信ネットワークは、ネットワーク利用度または空き容量の知識を考慮してキャッシング対象とするコンテンツ、キャッシング量またはキャッシュの再ポピュレート時期を決めることがない。]
[0008] コンテンツ配信ネットワークにおけるキャッシングはすべて、キャッシュに記憶されたコンテンツが今後使用されるだろうという前提に基づいているが、現在の実装は、かつて使用されたことのあるコンテンツアイテムが今後再び使用されること、またはあるユーザにとって興味深かったコンテンツアイテムが他のユーザにとっても興味深いことを想定して、どのコンテンツをキャッシュするかを決める。これらの実施形態は、単に直接的かつ非常に単純に将来のコンテンツ消費を予測しようとしており、そのために例えば、過去のコンテンツ消費を追跡して過去の消費アイテムのうちどれをキャッシュに保存すべきかを決める。]
[0009] どのコンテンツをキャッシュするかを決めるこの単純なプロセスは、いくつかの理由で失敗することがある。例えば、最近公開された映画は将来多くの視聴者を有すると予想され得るが、過去には視聴者がいなかった。したがって、既存のコンテンツ配信ネットワークは一般に、かかるコンテンツを記憶することができないと思われる。一方で、大半のコンテンツ配信ネットワークは、過去に人気があったコンテンツが将来には人気がなくなることを判断できないだろう。例えば、選挙期間中に広く関心が持たれる選挙特集は、選挙が終わればほとんどまたはまったく関心を寄せられないだろう。]
[0010] 別の例を挙げると、あるコンテンツ配信ネットワークのローカルサービスエリアに住んでいる唯一のカンボジア人であるカンボジア人女性は、カンボジア語のコンテンツを定期的に要求するかもしれない。しかし、彼女のコンテンツは近隣のユーザにとって興味深いものではなく、彼女は以前見たコンテンツを見たがらないと思われるため、彼女に配信されるアイテムをキャッシュすることにはほとんど有用性がない。既存のコンテンツ配信ネットワークは一般に、彼女固有の視聴パターンが彼女向けのコンテンツのキャッシングを役立たないものにしていることを認識できないだろう。]
[0011] また、既存のコンテンツ配信ネットワークが将来的に頻繁に使用される公算の大きいコンテンツアイテムを適切に特定した場合でも、こうしたネットワークはピーク使用時間中に当該アイテムを分散された記憶ポイントに送信する可能性があり、その結果、容量不足に拍車がかかることがある。また、既存のコンテンツ配信ネットワークは一般に、単一のネットワーキングモードで動作する。その結果、こうしたネットワークは、分散されたキャッシングポイントでブロードキャストネットワークから映画を記録することによってユニキャストダウンロードのネットワーク負荷の増大を回避できる場合でも、分散されたキャッシングポイントへの映画のユニキャストダウンロードを要求する可能性がある。]
発明が解決しようとする課題

[0012] ピーク外時間中にコンテンツを自動的にキャッシュするため、またはブロードキャストネットワークからのコンテンツを送信時に捕捉するために、将来のコンテンツ消費の予測知識を使用することにより、コストを軽減する予測キャッシング型コンテンツ配信ネットワークが必要である。また、現在のユーザの関心内容に合う可能性が最も高いコンテンツの在庫を維持するためにキャッシングを利用する自己適応型コンテンツ配信ネットワークが必要である。また、コンテンツ配信ネットワーク内で需要のピークを移行させ、それにより所与のネットワークリンク容量で配信できるサービスセッションの数を最大化するために選択済みコンテンツをキャッシュする必要もある。]
課題を解決するための手段

[0013] 前述の本発明の目的および利点は、様々な例示的実施形態によって達成できるものの例であり、実現可能な考え得る利点を網羅することも限定することも意図していない。よって、様々な例示的実施形態の上述および他の目的および利点は、本明細書の説明から明らかであると思われ、様々な例示的実施形態を実施することによって把握可能であり、いずれも本明細書で具体化されるか、当業者には明らかであり得る変形形態を考慮して変更され得る。したがって、本発明は、本明細書で示し、様々な例示的実施形態で説明する新たな方法、配列、組み合わせおよび改良の中に存在する。]
[0014] 予測キャッシング型コンテンツ配信ネットワークに対する現在のニーズを踏まえ、様々な例示的実施形態の概要を示す。以下の概要ではいくつかの単純化および省略をしているが、これは様々な例示的実施形態のいくつかの態様を強調し紹介することを意図しており、その範囲を限定することは意図していない。当業者が発明の概念を形成し使用できるだけの好ましい例示的実施形態の詳細な説明は、後のセクションで行う。]
[0015] 様々な現在の実施形態では、コンテンツ配信ネットワークはネットワークの近接性によりノードの階層で配置される。そのため、こうしたネットワークにおいてノードは、より近い場所でコンテンツの写しが得られない場合にのみ遠隔ノードからコンテンツをダウンロードする。階層において遠隔のノードからコンテンツアイテムを得る必要性を最小限にするため、コンテンツ配信ネットワークは、コンテンツアイテムをローカルキャッシュすることにより、トラフィックをピーク時間からピーク外時間に移行させる。]
[0016] 現在の様々な実施形態では、コンテンツ配信ネットワークは中間ノードを「通過する」コンテンツアイテムのコピーを保存するため通過キャッシングを利用する。ノードは、当該ノードを介して送信されるコンテンツのコピーを、かかるコンテンツへのアクセスがない時間が所定の時間に達するまで維持し、その時点で当該ノードはキャッシュからかかるコンテンツを除外する。こうした実施形態は、管理が容易であり、追加のネットワークトラフィックを生まないが、所与のコンテンツアイテムに対する最初の要求ではなく後続の要求への負荷を軽減するのに有用であるにすぎない。]
[0017] 現在の様々な実施形態では、コンテンツ配信ネットワークは代わりに、ユーザが視聴する現在のアイテムに基づきコンテンツアイテムをキャッシュするため予測プリフェッチを利用する。こうした実施形態はユーザ体験を向上させるが、常にネットワーク負荷を増大させることになり、どのコンテンツをキャッシュすべきかを決めるために将来のコンテンツアイテムに関する確率の予測を使用することはない。]
[0018] ブロードキャストコンテンツのキャッシングメカニズムは、インターネットプロトコルテレビジョン（ＩＰＴＶ）システムの現在の様々な実施形態で維持されている。かかるシステムでは、ビデオ画像を完全に更新するフレームを、１０秒を超える間隔で送信することができる。介入データにより、完全更新フレームは漸進的に変化するにすぎない。こうした実施形態では、「Ｄサーバ」は少数のビデオフレームをキャッシュし、高速チャネル変更を実現するためこれらのフレームをユニキャスト伝送でクライアントのセットトップボックスに送信する。最初の全画面更新フレームでは、クライアントはマルチキャストチャネルに参加し、Ｄサーバからのユニキャストストリームは止まる。しかし、こうした実施形態では、ネットワークは厳密な階層で配置され、その結果各Ｄサーバは定められた単一の親サーバを有する。よって、親サーバでコンテンツが入手できないとき、Ｄサーバは他のピアネットワークノードからコンテンツを取り出すことができない。また、チャネルが変更されたときにＤサーバからのユニキャストストリームは、クライアントが最終的に参加するマルチキャストチャネルよりも大きい帯域幅を占めるため、Ｄサーバでデータをキャッシュするとネットワークの効率性が損なわれる。さらに、ビデオチャネルの多くまたはすべてがＤサーバのサービス提供領域でユーザによって見られない場合でも、Ｄサーバはキャッシュ済みコンテンツの新鮮さを保つために各ビデオチャネルの供給を要求するため、Ｄサーバは通常、コンテンツソースに面する側でネットワークの効率性を低下させる。]
[0019] 現在の様々な実施形態では、パーソナルビデオレコーダは、記録するコンテンツの希望リストを作成し、当該コンテンツをブロードキャストスケジュールに現れたときに記録する。だが、こうした実施形態は、将来の視聴を予想してコンテンツアイテムを積極的に要求するわけではない。また、コンテンツは、ローカルまたは遠隔の場所ではなくユーザのパーソナルビデオレコーダに記憶されるにすぎない。よって、コンテンツは決して共有されないため、記憶領域の点でコスト的にかなり不利である。]
[0020] 現在の様々な実施形態では、Ｐ２Ｐファイル共有ネットワークにより、ユーザは単数または複数の他のユーザから得ることになる所望のコンテンツのリストを定めることができる。だが、こうした実施形態では、ユーザはコンテンツを明白に要求しなければならない。また、転送はネットワークの負荷またはコストを考慮せず、そのためネットワークサービスプロバイダに大きな悪影響を及ぼす。よって、Ｐ２Ｐネットワークはユーザエンドにのみ記憶装置を備え、全体のネットワーク容量およびコスト問題を無視する。]
[0021] 現在の様々な実施形態は、コンテンツ配信メカニズムとしてＰ２Ｐファイル共有の悪影響を軽減しようとしている。現在の様々な実施形態は、仲介者による攻撃によりＰ２Ｐプロトコルをインターセプトする。こうした実施形態は、ユーザのローカルネットワーク内で要求されたファイルの断片を見つけ、ローカルネットワーク内からファイルを調達する要求をリダイレクトする。したがって、コンテンツ配信ネットワークは、ローカルで取得できたであろうデータを調達するために広域ネットワークの高価なリンクまたは相互接続点（ｐｅｅｒｉｎｇ ｐｏｉｎｔｓ）をＰ２Ｐネットワークが使用することを妨げる。だが、こうした実施形態はネットワークでデータを実際に記憶することはなく、近接性を認識するデータの索引を提供するにすぎない。また、こうした実施形態は、アップロードがローカルの顧客からもたらされることを強いることによってローカルネットワークのコストを増大させ、これはアップロードの帯域幅に限りがあるネットワークでは特に厄介である。]
[0022] 現在の様々な実施形態は、複数のユーザへの配信用にＰ２Ｐファイルを記憶する、ローカル通過ネットワークのキャッシングポイントを作成する。こうした実施形態は、ローカルサーバ、典型的には中央局にファイルを格納し、それにより他のローカル顧客からの上流リンクの輻輳とＷＡＮリンクへの負荷の両方を回避する。だが、こうした実施形態は、事後にコンテンツをキャッシュするだけであり、それにより、達成可能な効率性を根本的に限定する。また、他のキャッシングシステムと同様、こうした実施形態はネットワーク負荷を考慮していない。]
[0023] 要約すると、上述の現在の実施形態は特に効果的なわけではなく、ネットワークの輻輳の増大につながることが多い。また、前述のキャッシングメカニズムのうち、キャッシングの効率性を最大化するためにユーザが要求しそうなコンテンツについて予測を利用するものはない。]
[0024] 上記にしたがい、様々な例示的実施形態は、経済的に最適な予測型コンテンツ配信ネットワークを作成すること、およびネットワーク状況が変化する中でこの最適状態を維持することを目的に、消費されそうなコンテンツアイテムの予測を利用するメカニズムを提供する。よって、決まった容量を持つネットワークリンクおよびコンテンツアイテムを記憶できるキャッシングノードからネットワークが成ることを踏まえ、様々な例示的実施形態は、ピーク時間に提供できるネットワークのサービス提供容量を最大化する。]
[0025] 様々な例示的実施形態は、ピーク外時間にコンテンツを動的に取り出すこと、またはブロードキャストネットワークから当該コンテンツを捕捉することを目的に、コンテンツアイテム消費の予測を利用する。様々な例示的実施形態では、各キャッシングノードは、こうした予測を利用してコンテンツアイテムをダウンロード、記録または除外するべきかを決定し、ピーク外時間に選択済みコンテンツアイテムをダウンロードする。]
[0026] ブロードキャストネットワークから記録することは、ピーク負荷に影響を与えないため、所望のコンテンツアイテムが送信されるときはいつでも発生し得る。マルチキャストや交換ブロードキャストなどの選択的な１対多の配信ネットワークモードから記録することは、以下の状況においてピーク負荷に影響を与えることなく生じ得る。ネットワークの一部における少なくとも１人の顧客が、コンテンツアイテムが生じるチャネルを見ているとき、送信が生じる時間がピーク外であるとき、または交換ブロードキャストまたはマルチキャストの帯域幅が最悪のピークに備えて常に確保されているよう、帯域幅のハードパーティショニングがあるとき。よって、様々な例示的実施形態では、キャッシングメカニズムは、リンク容量、スイッチングまたはルーティングの容量、およびコンテンツサービス提供容量を含むコストおよびサービスの容量に影響を与えるネットワーク負荷の全要素を認識し調整する。]
[0027] 様々な例示的実施形態では、コンテンツはコンテンツ配信ネットワーク内の様々な場所に記憶される。そのため、様々な例示的実施形態では、コンテンツは親キャッシングノード、ピアキャッシングノードから引き出され、またはブロードキャストもしくはマルチキャストのネットワークから記録される。また、様々な例示的実施形態では、コンテンツをユーザの場所またはサービスプロバイダのネットワーク内の多くの層に記憶することができる。]
[0028] 様々な例示的実施形態では、コンテンツ配信ネットワークは、コンテンツの記憶を最適化するため１つまたは複数の処理を実行する。そのため、様々な例示的実施形態では、キャッシングメカニズムは、キャッシングノード間で更新プロトコルを実行することによって、コンテンツの不要な重複を回避する。また、様々な例示的実施形態では、キャッシング容量がほぼ一杯の場合、およびより価値のあるコンテンツアイテムが記憶可能である場合に、キャッシングメカニズムは、記憶済みコンテンツアイテムを除外するハウスキーピング機能を実行する。]
[0029] 様々な例示的実施形態について一層理解できるよう、添付の図面を参照する。]
図面の簡単な説明

[0030] コンテンツの予測キャッシングを利用するコンテンツ配信ネットワークの例示的実施形態の概略図である。
コンテンツアイテムをユニキャストソースからキャッシュに追加またはキャッシュから除外する方法の例示的実施形態の流れ図である。
ユニキャストソースからコンテンツをキャッシュにダウンロードする方法の例示的実施形態の流れ図である。
コンテンツアイテムをブロードキャスト、交換ブロードキャストまたはマルチキャストのソースからキャッシュに追加またはキャッシュから除外する方法の例示的実施形態の流れ図である。
相互接続されたキャッシュのネットワークからコンテンツアイテムにアクセスする方法の例示的実施形態の流れ図である。
相互接続されたキャッシュのネットワークからコンテンツアイテムにアクセスする方法の例示的実施形態の流れ図である。
ノード間のアップデートの通信を行うコンテンツ配信ネットワークの例示的実施形態の概略図である。]
実施例

[0031] 次いで、同じ番号が同じ構成要素またはステップを指す図面を参照して、様々な例示的実施形態の幅広い態様を開示する。]
[0032] 本明細書で使用される以下の用語は、下記のとおり定義される。これらの定義の中で参照文字が指す対象については、以下でより詳細に説明する。]
[0033] ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）は、第１ローカルネットワーク記憶装置１０６から第１ユーザ記憶装置１０２へデータを送信するときの通信リンク１２０の容量を意味する。]
[0034] ＬｉｎｋＣａｐａｃｉｔｙ（Ｕ１→Ｌ１）は、第１ユーザ記憶装置１０２から第１ローカルネットワーク記憶装置１０６へデータを送信するときの通信リンク１２０の容量を意味する。]
[0035] ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ２）は、第１ローカルネットワーク記憶装置１０６から第２ユーザ記憶装置１０４へデータを送信するときの通信リンク１２２の容量を意味する。]
[0036] ＬｉｎｋＣａｐａｃｉｔｙ（Ｕ２→Ｌ１）は、第２ユーザ記憶装置１０４から第１ローカルネットワーク記憶装置１０６へデータを送信するときの通信リンク１２２の容量を意味する。]
[0037] リＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｌ２）は、第１ローカルネットワーク記憶装置１０６から第２ローカルネットワーク記憶装置１０８へデータを送信するときの通信リンク１２４の容量を意味する。]
[0038] ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ２→Ｌ１）は、第２ローカルネットワーク記憶装置１０８から第１ローカルネットワーク記憶装置１０６へデータを送信するときの通信リンク１２４の容量を意味する。]
[0039] ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｄ１）は、第１ローカルネットワーク記憶装置１０６から第１遠隔ネットワーク記憶装置１１０へデータを送信するときの通信リンク１２６の容量を意味する。]
[0040] ＬｉｎｋＣａｐａｃｉｔｙ（Ｄ１→Ｌ１）は、第１遠隔ネットワーク記憶装置１１０から第１ローカルネットワーク記憶装置１０６へデータを送信するときの通信リンク１２６の容量を意味する。]
[0041] ＳｅｒｖｉｃｉｎｇＣａｐａｃｉｔｙ（Ｄ１）は、第１遠隔ネットワーク記憶装置１１０におけるコンテンツサービス提供容量を意味する。]
[0042] ＳｅｒｖｉｃｉｎｇＣａｐａｃｉｔｙ（Ｌ１）は、第１ローカルネットワーク記憶装置１０６におけるコンテンツサービス提供容量を意味する。]
[0043] Ｓｔｏｒａｇｅ（Ｄ１）は、第１遠隔ネットワーク記憶装置１１０における記憶量を意味する。]
[0044] Ｓｔｏｒａｇｅ（Ｌ１）は、第１ローカルネットワーク記憶装置１０６における記憶量を意味する。]
[0045] Ｓｔｏｒａｇｅ（Ｕ１）は、第１ユーザ記憶装置１０２における記憶量を意味する。]
[0046] Ｓｔｏｒａｇｅ（Ｕ２）は、第２ユーザ記憶装置１０４における記憶量を意味する。]
[0047] ＳｗｉｔｃｈＣａｐａｃｉｔｙ（Ｄ１）は、第１遠隔ネットワーク記憶装置１１０におけるスイッチングまたはルーティングの容量を意味する。]
[0048] ＳｗｉｔｃｈＣａｐａｃｉｔｙ（Ｌ１）は、第１ローカルネットワーク記憶装置１０６におけるスイッチングまたはルーティングの容量を意味する。]
[0049] 図１は、コンテンツの予測キャッシングを利用するコンテンツ配信ネットワーク１００の例示的実施形態の概略図である。図１を参照して、例示的なコンテンツ配信ネットワーク１００の一般的動作および予測キャッシングプロセスについて説明する。] 図１
[0050] 例示的なコンテンツ配信ネットワーク１００は、第１ユーザ記憶装置１０２、第２ユーザ記憶装置１０４、第１ローカルネットワーク記憶装置１０６、第２ローカルネットワーク記憶装置１０８、第１遠隔ネットワーク記憶装置１１０および第２遠隔ネットワーク記憶装置１１２を含む。様々な例示的実施形態において、記憶装置がマルチメディアコンテンツのキャッシュを維持することを可能にする永久記憶装置を備えることが明らかであろう。また、様々な例示的実施形態において、各記憶装置は、コンテンツアイテムが当該ノードにローカル保存されているかを判断するための索引、およびローカル保存されていないコンテンツアイテムを探す場所を判断するための索引を備える。]
[0051] 様々な例示的実施形態において、各記憶装置は、通信リンクを介して１つまたは複数の他の記憶装置と通信することができる。そのため、例示的なコンテンツ配信ネットワーク１００において、第１ユーザ記憶装置１０２は通信リンク１２０を介して第１ローカルネットワーク記憶装置１０６と通信し、第２ユーザ記憶装置１０４は通信リンク１２２を介して第１ローカルネットワーク記憶装置１０６と通信し、第１ローカルネットワーク記憶装置１０６は通信リンク１２４を介して第２ローカルネットワーク記憶装置１０８と通信し、さらに通信リンク１２６を介して第１遠隔ネットワーク記憶装置１１０と通信し、第１遠隔ネットワーク記憶装置１１０は通信リンク１２８を介して第２遠隔ネットワーク記憶装置１１２と通信する。]
[0052] したがって、例示的なコンテンツ配信ネットワーク１００はキャッシングアーキテクチャにおいて４層を含む。キャッシングの第１レベルは第１ユーザ記憶装置１０２に対応しており、これは様々な例示的実施形態では、単一のユーザまたは世帯に固有のコンテンツを記憶する家庭用メディア記憶装置である。様々な例示的実施形態では、第１ユーザ記憶装置１０２はパーソナルコンピュータ、パーソナルビデオレコーダ、ホームメディアサーバ、内蔵記憶装置を備えたテレビ用セットトップボックス、ポータブルメディア装置、またはネットワーク通信能力を備えるその他の記憶装置であることが明らかであろう。]
[0053] 例示的なコンテンツ配信ネットワーク１００では、キャッシングの第２レベルは第２ユーザ記憶装置１０４のようなネットワークにおけるピアに対応する。キャッシングの第３レベルは、第１ローカルネットワーク記憶装置１０６および第２ローカルネットワーク記憶装置１０８のような、多くのユーザが接続しているローカルネットワークの中の中央ノードにある。最後に、キャッシングの第４レベルは、第１遠隔ネットワーク記憶装置１１０および第２遠隔ネットワーク記憶装置１１２のような、多くのローカルネットワーク記憶装置が接続している地域または国のノードにある。例示的なコンテンツ配信ネットワーク１００は、キャッシングにおいて４層を含むが、様々な例示的実施形態では、コンテンツ配信ネットワーク１００が、さらに遠隔の場所における追加の中央キャッシングサーバを含むよう拡張されることが明らかであろう。また、様々な例示的実施形態において、コンテンツ配信ネットワーク１００は、層の１つまたは複数において３つ以上のノードを含む。]
[0054] 図２は、コンテンツアイテムをユニキャストソースからキャッシュに追加またはキャッシュから除外する方法２００の例示的実施形態の流れ図である。様々な例示的実施形態において、例示的方法２００は、上流ソースからの新たなアイテムをキャッシュすべきか決定する。例示的実施方法２００は、コンテンツをキャッシュする能力を有するコンテンツ配信ネットワーク内の任意のノードで実行できることが明らかであろう。そのため、様々な例示的実施形態では、例示的方法２００は、第１ユーザ記憶装置１０２、第２ユーザ記憶装置１０４、第１ローカルネットワーク記憶装置１０６、第２ローカルネットワーク記憶装置１０８、第１遠隔ネットワーク記憶装置１１０および第２遠隔ネットワーク記憶装置１１２の１つまたは複数で実行される。] 図２
[0055] 例示的方法２００は、定期的な間隔で、または将来のコンテンツアクセスの確率に影響を与える変化が生じたときに、ステップ２０１で始まる。そのため、様々な例示的実施形態では、例示的方法２００は、１時間に１回、１日１回、または他の所定の時間間隔で実行される。また、様々な例示的実施形態では、例示的方法２００は、新たなマルチメディアコンテンツが公開されたとき、またはユーザが例えば特定のジャンルの映画もしくは音楽に関心を示したときに実行され、それによりこうした種類のコンテンツアイテムをキャッシュする価値の予測を変更する。]
[0056] 次いで例示的方法２００はステップ２０２に進み、未使用容量、使用容量、およびノードに現在キャッシュされている全アイテムの有用性を判断するためのチェックが実行される。有用性は一般に、当該コンテンツアイテムを使用し得るユーザの数と各ユーザが当該コンテンツアイテムを使用する可能性との組み合わせに基づく。様々な例示的実施形態で、有用性はまた、ネットワークによるピーク需要を軽減する際、またはユーザに提供され得るコンテンツアイテムの品質を高める際の効果の点で、分散された記憶装置からコンテンツアイテムを入手できることの価値など、他の要素を含む。ステップ２０２に続き、例示的方法２００はステップ２０４に進み、ノードは、有用性の最も高いコンテンツアイテムのリストを作成する。]
[0057] キャッシュが第１ユーザ記憶装置１０２のようなユーザノードであるとき、様々な例示的実施形態では、有用性の最も高いコンテンツアイテムのリストは、そのユーザまたは世帯のみに関係する。様々な例示的実施形態において、キャッシュが第１ローカルネットワーク記憶装置１０６のようなネットワークノードであるとき、有用性の最も高いコンテンツアイテムのリストは、使用の累積確率、またはより一般的には、サポートされるユーザノードの各々からのリストによって形成される有用性を示す尺度である。一般に、こうしたユーザノードに記憶済みのコンテンツアイテムには、同じコンテンツアイテムの新たなコピーを保存することに伴う有用性はない。]
[0058] そのため、様々な例示的実施形態において、有用性の最も高いコンテンツアイテムのリストは、あるアイテムがキャッシングノードに対し要求される確率またはかかるアイテムの新たなインスタンスをキャッシュする有用性を反映しており、その結果、ユーザの近くでキャッシュ済みのアイテムを排除する。様々な例示的実施形態において、ステップ２０４は、希少性に関する自立的な階層を生成する。つまり、アクセス確率の高いコンテンツアイテムは、ユーザの近くでキャッシュされる傾向があり、めったにアクセスされないアイテムは、より中心的な場所、例えば第１遠隔ネットワーク記憶装置１１０に記憶される。様々な例示的実施形態において、ごく一部のユーザにとってアクセス確率の高いコンテンツアイテムがあるときは、当該コンテンツアイテムは、好みによりレベル１、例えば第１ユーザ記憶装置１０２でキャッシュされる。一方、多くのユーザにとってアクセス確率の高いコンテンツアイテムがある場合、当該コンテンツアイテムは、好みによりレベル３、例えば第１ローカルネットワーク記憶装置１０６でキャッシュされる。]
[0059] 様々な例示的実施形態において、有用性の最も高いコンテンツアイテムのリストは、当該アイテムがピーク時間中にアクセスされる確率を反映するため、さらに精緻化される。そのため、様々な例示的実施形態において、有用性の最も高いコンテンツアイテムのリストは、負担軽減効果をさらに高める。]
[0060] 有用性の最も高いコンテンツアイテムのリストを作成した後、例示的方法２００はステップ２０６に進み、ノードは、有用性の最も高いコンテンツアイテムのリストとノードに現在キャッシュされているコンテンツのリストとを比較する。様々な例示的実施形態において、ノードに現在キャッシュされているコンテンツのリストは、図４を参照して以下でさらに説明するとおり、将来のある時点におけるブロードキャスト、交換ブロードキャストまたはマルチキャストのネットワークからの記録がスケジュールされているアイテムを含む。] 図４
[0061] 比較後、例示的方法２００はステップ２０８に進み、ノードはキャッシング候補のコンテンツアイテムの順位リストを生成し、このリストは、様々な実施形態において、有用性の最も高いコンテンツアイテムのリストから当該ノードで現在キャッシュされているコンテンツのリストを除いたものを含む。そのため、様々な例示的実施形態において、キャッシング候補のコンテンツアイテムの順位リストは、有用性の最も高いコンテンツアイテムのリストの中で当該ノードで現在キャッシュされていない全アイテムを含む。様々な例示的実施形態において、キャッシング候補リストは、コンテンツアイテムの識別子および各コンテンツアイテムの使用確率を示す有用性の尺度を含む。]
[0062] 様々な例示的実施形態において、ステップ２０８では、キャッシング候補リストの順位付けにおいて各アイテムの大きさを考慮することもできる。そのため、様々な例示的実施形態において、大きなコンテンツアイテムと、アクセス確率がほぼ同じでこれより小さいコンテンツアイテムのグループとの間でノードが選択しなければならない場合、小さいコンテンツアイテムのグループがより高い順位を付けられ、それにより複数のアイテムのうちの１つがアクセスされる確率が高まる。]
[0063] キャッシング候補リストの生成後、例示的方法２００はステップ２１０に進み、ノードは、現在の時間がピーク外時間にあるか判断する。ステップ２１０において、現在の時間はピーク外時間でないとノードが判断したとき、ノードはコンテンツをダウンロードしない。その結果、例示的方法２００はステップ２１３に進み、例示的方法２００は終了する。様々な例示的実施形態において、次の時間帯がピーク時間であっても、例示的方法２００はステップ２１２に進むが、それは将来のピーク外時間におけるダウンロードをスケジュールできるようにするためにすぎないことが明らかであろう。]
[0064] ステップ２１０において、次の時間帯がピーク外時間であるとノードが判断したとき、例示的方法２００はステップ２１２に進み、ノードはキャッシュにコンテンツをダウンロードする。様々な例示的実施形態では、最小限の時間でダウンロードが完了する場合、または将来のある時点でのダウンロードがスケジュールされている場合、当該ノードのコンテンツインベントリへの入力では、コンテンツアイテムを「保留」として記録し、その結果、同じコンテンツアイテムを取り出そうとする並行した試みは阻止される。次いで例示的方法はステップ２１３に進み、例示的方法２００は終了する。]
[0065] 図３は、ユニキャストソースからコンテンツをキャッシュにダウンロードする方法２１２の例示的実施形態の流れ図である。例示的方法２１２はステップ３０１で始まり、ステップ３０２に進み、リンク、スイッチおよびサーバを含むすべての上流構成要素が空き容量を示しているかをノードが判断する。ステップ３０２において、１つまたは複数のリンク、スイッチまたはサーバが空き容量のないことを示しているとノードが判断した場合、例示的方法２１２はステップ３１４に進み、例示的方法２１２は終了する。ステップ３０２においてすべてのリンク、スイッチおよびサーバが空き容量を示しているとノードが判断した場合、例示的方法２１２はステップ３０４に進む。] 図３
[0066] 様々な例示的実施形態では、ステップ３０４において、キャッシング候補コンテンツアイテムのリストによる最高順位のコンテンツアイテムを記憶する十分な空き記憶容量をキャッシュが有するかをノードが判断する。ステップ３０４において、十分な空き容量があるとノードが判断した場合、例示的方法２１２はステップ３１０に進み、ノードは上流ノードからキャッシュに最高順位のアイテムをダウンロードする。]
[0067] 様々な例示的実施形態では、ステップ３１０においてアイテムがダウンロードされると、例示的方法２１２はステップ３１２に進み、コンテンツアイテムは、当該アイテムが置換されない保持時間を割り当てられる。かかる実施形態では、保持時間が終了していない場合、新たなアイテムの確率から保存済みアイテムの確率を差し引いた値が所定のスワップしきい値を超えていない限り、コンテンツアイテムはキャッシュから除外されない。そのため、こうした実施形態では、例示的方法２１２は「チャーニング（ｃｈｕｒｎｉｎｇ）」というプロセスを回避する。チャーニングプロセスでは、コンテンツアイテムは繰り返しダウンロードされ、同程度の順位の別のコンテンツアイテムを優先して除外される。次いで、例示的方法２１２はさらなる処理のためステップ３０２に戻る。]
[0068] ステップ３０４において、空き記憶容量が不十分だとノードが判断した場合、例示的方法２１２はステップ３０６に進む。様々な例示的実施形態では、ステップ３０６において、最高順位の候補コンテンツアイテムの有用性が、当該候補アイテムと同じかそれより大きい規模のキャッシュ済み最下位アイテム有用性を、少なくともスワップしきい値だけ高い有用性を有するかをノードが判断する。こうした有用性の低いキャッシュ済みアイテムが発見された場合、例示的方法２１２はステップ３０８に進み、有用性の低いキャッシュ済みアイテムは除外される。]
[0069] 有用性の低いキャッシュ済みアイテムが見つからなかった場合、最高順位の候補コンテンツアイテムは、当該候補コンテンツアイテムよりも全体として規模が大きい１組のキャッシュ済みアイテムと比較される。最高順位の候補コンテンツアイテムの有用性が、選択された１組のキャッシュ済みアイテムの全体の有用性を、少なくともスワップしきい値だけ上回る場合、例示的方法２１２はステップ３０８に進み、ノードは１組のキャッシュ済みの有用性の低いアイテムを除外する。]
[0070] 有用性の低いアイテムをキャッシュから除外した後、例示的方法２１２はステップ３１０に進み、ノードは最高順位のアイテムをダウンロードする。ダウンロードと除外の手順を実行した後、例示的方法２１２はアイテムのチャーニングの可能性を低下させるためアイテム最小保持時間を選択的に割り当て、キャッシュから新鮮でないコンテンツアイテムを定期的に除去できるよう最大保持時間を選択的に割り当てる。次いで、例示的方法２１２はステップ３０２に進み、ネットワークがピーク外時間にある場合には次の潜在的コンテンツアイテムが検討される。]
[0071] ステップ３０６において、最高順位のコンテンツアイテムの規模より全体の規模が大きく、かつ有用性の低いアイテムをノードが見つけなかった場合、例示的方法はステップ３１４に進み、例示的方法２１２は終了する。]
[0072] 図４は、コンテンツアイテムをブロードキャストまたはマルチキャストのソースからキャッシュに追加またはキャッシュから除外する方法４００の例示的実施形態の流れ図である。様々な例示的実施形態において、例示的方法４００は、新たなアイテムをブロードキャスト、交換ブロードキャストまたはマルチキャストのソースから記録することによってキャッシュすべきかを判断する。例示的実施形態４００は、コンテンツをキャッシュする能力を有するコンテンツ配信ネットワーク内の任意のノードで実行できることが明らかであろう。そのため、様々な例示的実施形態では、例示的方法４００は、第１ユーザ記憶装置１０２、第２ユーザ記憶装置１０４、第１ローカルネットワーク記憶装置１０６、第２ローカルネットワーク記憶装置１０８、第１遠隔ネットワーク記憶装置１１０および第２遠隔ネットワーク記憶装置１１２の１つまたは複数で実行される。] 図４
[0073] 例示的方法４００は、定期的な間隔で、または将来のコンテンツアクセスの確率に影響を与える変化が生じたときに、ステップ４０１で始まる。そのため、様々な例示的実施形態では、例示的方法４００は、１時間に１回、１日１回または他の所定の時間間隔で実行される。また、様々な例示的実施形態では、新たなマルチメディアコンテンツアイテムが公開されたとき、ブロードキャスト／交換ブロードキャスト／マルチキャストの配信スケジュールが変更もしくは延長されて将来に新たな時間帯を対象とするようになったとき、ユーザが例えば特定のジャンルの映画もしくは音楽に興味を示したとき、またはその他の動きがきっかけでユーザが所与のコンテンツアイテムにアクセスする確率を再評価することになったとき、例示的方法４００は実行される。]
[0074] 次いで例示的方法４００はステップ４０２に進み、未使用容量、使用容量、およびノードに現在キャッシュされている全アイテムの有用性を判断するためのチェックが実行される。ステップ４０２に続き、例示的方法４００はステップ４０４に進み、ノードは、ブロードキャスト／マルチキャストの配信スケジュールに現れるコンテンツアイテムから有用性の最も高いコンテンツアイテムのリストを作成する。様々な例示的実施形態では、ステップ４０４において、ノードは例えば電子プログラムガイドからブロードキャストまたはマルチキャストのコンテンツ配信スケジュールを取得する。]
[0075] 様々な例示的実施形態では、ステップ４０４において、ノードは、ノードからコンテンツを引き出す全ユーザにおける特定のユーザの関心を、入手可能なブロードキャストまたはマルチキャストのコンテンツのスケジュールにおけるコンテンツアイテムと比較することによって、有用性の最も高いコンテンツアイテムのリストを作成する。様々な例示的実施形態において、ユーザの関心は、好みのジャンル、映画、テレビショー、チャネル、俳優、監督、およびコンテンツアイテムを分類または区別するために使用できるその他の基準の１つまたは複数を含む。また、様々な例示的実施形態では、関心は、ユーザによって特定され、またはユーザの過去のコンテンツ選択に基づき予測される。]
[0076] キャッシュが第１ユーザ記憶装置１０２のようなユーザノードであるとき、様々な例示的実施形態では、有用性の最も高いコンテンツアイテムのリストは、そのユーザまたは世帯のみに関係する。様々な例示的実施形態において、キャッシュが第１ローカルネットワーク記憶装置１０６のようなネットワークノードであるとき、有用性の最も高いコンテンツアイテムのリストは、サポートされるユーザノードの各々からのリストによって形成される累積有用性を表す。]
[0077] ステップ４０４において有用性の最も高いコンテンツアイテムのリストを作成した後、例示的方法４００はステップ４０６に進み、ノードは、有用性の最も高いコンテンツアイテムのリストとノードに現在キャッシュされているコンテンツのリストとを比較する。比較後、例示的方法４００はステップ４０８に進み、ノードは、様々な例示的実施形態において、有用性の最も高いコンテンツアイテムのリストから当該ノードで現在キャッシュされているコンテンツのリストを除いた、キャッシング候補の順位リストを生成する。そのため、様々な例示的実施形態において、キャッシング候補の順位リストは、有用性の最も高いコンテンツアイテムのリストの中で当該ノードで現在キャッシュされていないアイテムすべてを含む。様々な例示的実施形態では、キャッシング候補リストは、アイテムの大きさ、ユーザ数およびアイテムの使用可能性に基づくアイテムの有用性、ならびにアイテムがアクセスされ得る時間、日およびチャネルを含む。]
[0078] 次いで、例示的方法４００はステップ４１０に進み、ノードは、キャッシング候補アイテムのリストが空であるか判断する。ステップ４１０において、キャッシング候補のリストが空であるとノードが判断した場合、例示的方法４００はステップ４２１に進み、ノードは、新たなアイテムの場所を作るために除外がスケジュールされたアイテムを除外する。次いで、例示的方法４００はステップ４２２に進み、記録がスケジュールされたアイテムが記録される。スケジュールされたアイテムを記録した後、例示的方法４００はステップ４２４に進み、記録されたアイテムは保持時間を割り当てられる。ステップ４２４において、例示的方法４００はアイテムのチャーニングの可能性を低下させるため最小保持時間をアイテムに選択的に割り当て、キャッシュから新鮮でないコンテンツアイテムを定期的に除去できるよう最大保持時間を選択的に割り当てる。次いで例示的方法４００はステップ４２６に進み、例示的方法４００は終了する。]
[0079] ステップ４１０において、検討すべき候補コンテンツアイテムがあるとノードが判断した場合、例示的方法４００はステップ４１２に進み、候補コンテンツアイテムがアクセスされ得る時がピーク外時間にあるかをノードは判断する。このステップは、マルチキャストネットワークや交換ブロードキャストネットワークなどの、配信が裁量的なネットワークに当てはまることが明らかであろう。一般にブロードキャストネットワークに当てはまるような、常に同じ容量（例：チャネル数）を使用するネットワークは、アイテムをキャッシュに記録してもネットワーク負荷に影響を与えないため、常にピーク外にあると考えることができる。また、交換ブロードキャストまたはマルチキャストのネットワークは、その時点で他の視聴者がいる場合に追加の負荷を経験せず、そのため、他の視聴者が予想される場合、コンテンツアイテムはいつアクセスされるかにかかわらずピーク外にあると考えられる。交換ブロードキャストまたはマルチキャストのネットワークはまた、ネットワークプロバイダが帯域幅のハードパーティショニングを行い、それにより帯域幅が常に最悪のチャネル負荷に備えて確保されている場合、ピーク外にあると考えられる。この場合、コンテンツアイテムを記録しても、必要な帯域幅に影響を与えない。]
[0080] ステップ４１２において、コンテンツアイテムがアクセスされ得る時間がピーク時間であるとノードが判断した場合、ノードはコンテンツアイテムの記録をスケジュールせず、例示的方法４００はステップ４１０に戻り、次の候補コンテンツアイテムが検討される。単一のコンテンツアイテムは異なる時点に複数のチャネルで配信することができるため、単一のコンテンツアイテムは、ステップ４１０で複数回、すなわち各々の可能な時間帯ごとに１回検討しなければならない場合もあることが明らかであろう。]
[0081] ステップ４１２において、コンテンツアイテムがアクセスされ得る時間がピーク外時間であるとノードが判断した場合、例示的方法４００はステップ４１４に進み、キャッシング候補コンテンツアイテムのリストによる最高順位のコンテンツアイテムを記憶するための十分な空き記憶容量がキャッシュにあるかをノードは判断する。ステップ４１４において、十分な空き記憶容量があるとノードが判断した場合、例示的方法４００はステップ４１５に進み、記憶容量が確保される。次いで、例示的方法４００はステップ４２０に進み、ノードは、最高順位のアイテムが送信される日、時間およびチャネルにおいて当該コンテンツアイテムをキャッシュに記録することをスケジュールする。次いで例示的方法４００はステップ４１０に戻り、例示的方法４００は他のコンテンツアイテムを検討する。]
[0082] ステップ４１４において、空き記憶容量が不十分だとノードが判断した場合、例示的方法４００はステップ４１６に進む。様々な例示的実施形態では、ステップ４１６において、最高順位の候補の新コンテンツアイテム有用性が、当該候補アイテムと同じかそれより大きい規模のキャッシュ済み最下位アイテム有用性を少なくともスワップしきい値だけ高い有用性を有するかをノードが判断する。こうした有用性の低いキャッシュ済み当該コンテンツアイテムが発見された場合、例示的方法４００はステップ４１８に進み、有用性の低いキャッシュ済みアイテムの除外がスケジュールされる。次いで、例示的方法４００はステップ４２０に進み、候補コンテンツアイテムの記録がスケジュールされ、そしてステップ４１０に進み、次の候補コンテンツアイテムが検討される。]
[0083] 有用性の低い単一コンテンツアイテムが現在記憶されていない場合、最高順位の候補の新コンテンツアイテムは、かかる候補の新コンテンツアイテムよりも全体的に大きい１組のキャッシュ済みアイテムと比較される。最高順位の候補の新コンテンツアイテムの有用性が、１組のキャッシュ済みアイテムの全体の有用性を少なくともスワップしきい値だけ上回る場合、例示的方法４００はステップ４１８に進む。ステップ４１８では、有用性の低い１組のキャッシュ済みアイテムの除外がスケジュールされる。次いで、例示的方法４００はステップ４２０に進み、候補コンテンツアイテムの記録がスケジュールされ、そしてステップ４１０に進み、次の候補コンテンツアイテムが検討される。]
[0084] ステップ４１６において、既存の１つまたは複数のアイテムを除外しないことが決まった場合、例示的方法４００はステップ４１０に戻り、次の候補コンテンツアイテムが検討される。]
[0085] 明確にするため別個に説明したが、様々な例示的実施では、図２および４を参照して説明した例示的方法２００、４００は、同じエンドユーザのために同じ記憶装置に情報をキャッシュすることが明らかであろう。また、様々な例示的実施形態では、図２−４を参照して説明した方法は、ステップ２０６および４０６において統合され、その結果、所与のコンテンツアイテムは１回だけ取り出され記憶される。また、様々な例示的実施形態では、例示的方法２００、４００はコンテンツアイテムの有用性を計算するのに同じ技法を利用し、その結果、記憶容量が限られている場合にどのコンテンツアイテムが最も価値があり保持すべきかについて常に合意がある。] 図２
[0086] 図５Ａおよび図５Ｂは、相互接続されたキャッシュのネットワークからコンテンツアイテムにアクセスする方法５００の例示的実施形態の流れ図である。例示的方法５００は、図５Ａのステップ５０１で始まり、ステップ５０２に進み、ノードは第１ユーザ記憶装置１０２にアクセスする。次いで例示的方法はステップ５０４に進み、例示的方法５００は、要求されたコンテンツが第１ユーザ記憶装置１０２で入手できるか判断する。ステップ５０４において、当該コンテンツが第１ユーザ記憶装置１０２で入手できるとノードが判断した場合、本方法はステップ５２５に進み、例示的方法５００は終了する。] 図５Ａ 図５Ｂ
[0087] ステップ５０４において、要求されたコンテンツがユーザノードで入手できないとノードが判断した場合、本方法はステップ５０６に進み、ノードは第１ローカルネットワーク記憶装置１０６にアクセスする。次いで例示的方法５００はステップ５０８に進み、様々な例示的実施形態において、例示的方法５００は、要求されたコンテンツアイテムが第１ローカルネットワーク記憶装置１０６にキャッシュされているか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）が通信リンク１２０の全セッションによって使用される容量より大きいか、またＳｅｒｖｉｃｉｎｇＣａｐａｃｉｔｙ（Ｌ１）が第１ローカルネットワーク記憶装置１０６から提供される全ユーザセッションの合計より大きいかを判断する。ステップ５０８において、全条件が満たされている場合、例示的方法５００は第１ローカルネットワーク記憶装置１０６からコンテンツをダウンロードし、ステップ５２５に進み、例示的方法５００は終了する。]
[0088] ステップ５０８において、１つまたは複数の条件が満たされていない場合、例示的方法５００はステップ５１０に進み、ノードは第２ユーザ記憶装置１０４にアクセスする。次いで例示的方法５００はステップ５１２に進み、様々な例示的実施形態では、例示的方法５００は、要求されたコンテンツアイテムが第２ユーザ記憶装置１０４にキャッシュされているか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）が通信リンク１２０の全セッションによって使用される容量より大きいか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｕ２→Ｌ１）が通信リンク１２２の全セッションによって使用される容量より大きいか、またＳｗｉｔｃｈＣａｐａｃｉｔｙ（Ｌ１）が第１ローカルネットワーク記憶装置１０６の交換トラフィック全体の合計よりも大きいかを判断する。ステップ５１２において、全条件が満たされている場合、例示的方法５００は第１ローカルネットワーク記憶装置１０６を介して第２ユーザ記憶装置１０４からコンテンツをダウンロードし、ステップ５２５に進み、例示的方法５００は終了する。]
[0089] ステップ５１２において、１つまたは複数の条件が満たされていない場合、例示的方法５００は図５Ｂのステップ５１４に進み、ノードは複数のユーザノードにアクセスする。次いで例示的方法５００はステップ５１６に進み、様々な例示的実施形態では、例示的方法５００は、要求されたコンテンツアイテムがユーザノードの２つ以上に断片的にキャッシュされているか判断する。様々な例示的実施形態では、ステップ５１６において、ノードはまた、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）が通信リンク１２０の全セッションによって使用される容量より大きいか、Ｕｉがｉ番目のユーザノードである場合にＬｉｎｋＣａｐａｃｉｔｙ（Ｕｉ→Ｌ１）が各通信リンクの全セッションによって使用される容量より大きいか、またＳｗｉｔｃｈＣａｐａｃｉｔｙ（Ｌ１）が第１ローカルネットワーク記憶装置１０６の交換トラフィック全体の合計よりも大きいかを判断する。ステップ５１６において、全条件が満たされている場合、例示的方法５００は分散されたユーザノードからコンテンツをダウンロードし、ステップ５２５に進み、例示的方法５００は終了する。] 図５Ｂ
[0090] ステップ５１６において、１つまたは複数の条件が満たされていない場合、例示的方法５００はステップ５１８に進み、ノードは第２ローカルネットワーク記憶装置１０８にアクセスする。次いで例示的方法５００はステップ５２０に進み、様々な例示的実施形態では、例示的方法５００は、要求されたコンテンツアイテムが第２ローカルネットワーク記憶装置１０８にキャッシュされているか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）が通信リンク１２０の全セッションによって使用される容量より大きいか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ２→Ｌ１）が通信リンク１２４の全セッションによって使用される容量より大きいか、またＳｗｉｔｃｈＣａｐａｃｉｔｙ（Ｌ１）が第１ローカルネットワーク記憶装置１０６の交換トラフィック全体の合計よりも大きいかを判断する。ステップ５２０において、全条件が満たされている場合、例示的方法５００は第１ローカルネットワーク記憶装置１０６を介して第２ローカルネットワーク記憶装置１０８からコンテンツをダウンロードし、ステップ５２５に進み、例示的方法５００は終了する。]
[0091] ステップ５２０において、１つまたは複数の条件が満たされていない場合、例示的方法５００はステップ５２２に進み、ノードは第１遠隔ネットワーク記憶装置１１０にアクセスする。次いで例示的方法５００はステップ５２４に進み、様々な例示的実施形態では、例示的方法５００は、要求されたコンテンツアイテムが第１遠隔ネットワーク記憶装置１１０にキャッシュされているか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１→Ｕ１）が通信リンク１２０の全セッションによって使用される容量より大きいか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｄ１→Ｌ１）が通信リンク１２６の全セッションによって使用される容量より大きいか、ＬｉｎｋＣａｐａｃｉｔｙ（Ｌ１）が第１ローカルネットワーク記憶装置１０６の交換トラフィック全体の合計よりも大きいか、またＳｅｒｖｉｎｇＣａｐａｃｉｔｙ（Ｄ１）が第１遠隔ネットワーク記憶装置１１０から提供される全ユーザセッションの合計よりも大きいかを判断する。ステップ５２０において、全条件が満たされている場合、例示的方法５００は第１ローカルネットワーク記憶装置１０６を介して第１遠隔ネットワーク記憶装置１１０からコンテンツをダウンロードし、ステップ５２５に進み、例示的方法５００は終了する。]
[0092] ステップ５２４において、１つまたは複数の条件が満たされていない場合、例示的方法５００はユーザに対し、要求されたコンテンツアイテムが入手できないため、またはネットワーク容量が不十分なためダウンロードが不成功だったことを通知する。次いで例示的方法５００はステップ５２５に進み、例示的方法５００は終了する。]
[0093] 図６は、ノード間のアップデートの通信を行うコンテンツ配信ネットワーク６００の例示的実施形態の概略図である。] 図６
[0094] 例示的なコンテンツ配信ネットワーク６００は、ユーザ記憶装置６０２、ローカル記憶装置６０４、ローカルピア記憶装置６０６および遠隔記憶装置６０８を含む。様々な例示的実施形態において、各記憶装置は、通信リンクを介して１つまたは他の記憶装置と通信することができる。そのため、例示的なコンテンツ配信ネットワーク６００では、ユーザ記憶装置６０２は通信リンク６１０を介してローカル記憶装置６０４と通信し、ローカル記憶装置６０４は通信リンク６１２を介してローカルピア記憶装置６０６と通信し、ローカル記憶装置６０４は通信リンク６１４を介して遠隔記憶装置６０８と通信する。]
[0095] 様々な例示的実施形態では、コンテンツ配信ネットワーク６００の各ノードは、当該ノードに記憶されているコンテンツについて近隣ノードに知らせるため１つまたは複数の形式のアップデートメッセージを提供する。そのため、様々な例示的実施形態では、コンテンツ配信ネットワーク６００の各ノードは、当該ノードに記憶されており、各々が索引識別子によって識別されるコンテンツアイテムすべてのリストである完全なアップデートを提供する。様々な例示的実施形態では、任意のノードは１つまたは複数の近隣ノードに対し、いつでも完全なアップデートの要求を送信することができる。また、様々な例示的実施形態では、新たなノードがコンテンツ配信ネットワーク６００にインストールされたときに完全アップデート手順が実行される。]
[0096] 様々な例示的実施形態では、コンテンツ配信ネットワーク６００の各ノードは、前回のメッセージ以降に追加または除外されたコンテンツについて近隣ノードに知らせる増分アップデートを提供する。増分アップデートを通信するために、様々な例示的実施形態では、ノードは「追加ａ、ｂ、ｃ、除外ｅ、ｆ、ｇ」（ａ−ｇはコンテンツアイテム識別子）という形式でメッセージを送信する。また、様々な例示的実施形態では、こうしたメッセージはＸＭＬまたはＳＯＡＰファイルにＡＳＣＩＩテキスト列を組み込むことによって通信される。]
[0097] 様々な例示的実施形態では、アップデートの通知は、ユーザ記憶装置６０２とローカル記憶装置６０４との間で通信リンク６１０を介して双方向で発生する。また、様々な例示的実施形態では、アップデートの通知は、ローカル記憶装置６０４と遠隔記憶装置６０８との間で通信リンク６１４を介して双方向で発生する。様々な例示的実施形態では、アップデートの通知は、ローカル記憶装置６０４からローカルピア記憶装置６０６への方向でのみ通信リンク６１２を介して発生する。]
[0098] 様々な例示的実施形態では、各ノードはキャッシュする意向を通信する追加のメッセージ型をサポートする。そのため、様々な例示的実施形態では、ノードは他のノードに対し、今度のブロードキャストまたはマルチキャストのプログラムを記録する意向を示すメッセージを送信する。したがってノードは、人気のあるアイテムを特定するため近隣ノードからのキャッシング候補リストをチェックし、将来の要求を容易にするためにアイテムをキャッシュすることができる。]
[0099] 様々な例示的実施形態では、コンテンツ配信ネットワーク６００の各ノードは、通信リンク６１０、通信リンク６１２および通信リンク６１４の１つまたは複数を介してネットワーク利用度に関して近隣ノードに知らせるため１つまたは複数の形式のアップデートメッセージを提供する。様々な例示的実施形態では、利用度は、リンク利用度、スイッチングまたはルーティングの利用度、およびコンテンツサーバ利用度を含む、コンテンツ配信能力を反映した全要素を組み込んだ個別的または複合的尺度である。そのため、様々な例示的実施形態では、利用度情報は、使用可能容量全体に対するノードで使用中の使用可能容量の一部を含む。また、様々な例示的実施形態では、利用度情報は、通信リンクを介して容量が使用可能か否かを示す真または偽の値である。]
[0100] 様々な例示的実施形態では、ノードは１つまたは複数の近隣ノードに対し、ネットワーク状況に関するアップデートの要求を送信することができる。対照的に、様々な例示的実施形態では、ノードは近隣ノードに対し自動的にアップデートを送信する。様々な例示的実施形態では、アップデートメッセージは定期的なアップデートであり、定期的な間隔で利用度状況を通知する。また、様々な例示的実施形態では、アップデートメッセージは警告型アップデートであり、ネットワーク利用度が臨界点に達したこと、および任意のトラフィックをすべて回避すべきことを近隣ノードに通知する。また、様々な例示的実施形態では、こうしたメッセージはＸＭＬまたはＳＯＡＰファイルにＡＳＣＩＩテキスト列を組み込むことによって通信される。そのため、様々な例示的実施形態では、メッセージは「Ｌ１ＯＫ」または「Ｌ１→Ｕ１６５％、Ｌ１スイッチング４３％、Ｌ１サーバ３９％」と同様の形式である。]
[0101] 上記を踏まえ、コンテンツ配信ネットワークの機能の例は以下のとおりとなる。第１ユーザ記憶装置１０２に位置するユーザが新たなコメディ映画を好むことを示す特徴を有すると仮定する。新たなコメディ映画「エバンオールマイティ」は入手可能となり、そのため即座にユーザの「視聴見込み」リスト最上位近くに達する。]
[0102] 第１ユーザ記憶装置１０２はユーザのホームメディアサーバであり、フィルムが保持され得る第１ノードである。ユーザのホームメディアサーバを含むネットワークの各ノードは、以下を含むことができる：当該ノードにローカル保存されているコンテンツアイテムの記憶容量、コンテンツアイテムが当該ノードにローカル保存されているか判断するための索引、およびローカル保存されていないコンテンツアイテムを探す場所を判断するための索引。]
[0103] 第１ローカルネットワーク記憶装置１０６は、第２ユーザ記憶装置１０４、第２ローカルネットワーク記憶装置１０８および第１遠隔ネットワーク記憶装置１１０のどこで「エバンオールマイティ」を探すべきかを特定する索引を維持している。各ノードに記憶されているコンテンツは継続的に変化するため、ノードが隣接ノードに対し、当該ノードからまたは当該ノードを通じてどんなコンテンツに到達し得るかを通信できるよう、アップデートプロトコルが提供される。]
[0104] どんなコンテンツが必要かについての決定は、単なる個々のユーザではなく各ユーザの需要予測を総合したものによってなされる。そのため、ネットワークまたは顧客の場所に位置する決定ポイントは、ユーザおよびその他の顧客の将来のコンテンツ需要を予測する。要求された１組のコンテンツは、より遠隔のノードにネットワークを介してカスケードし、他の対象ユーザの要求されたコンテンツを追加し、中間ノードにキャッシュ済みのコンテンツを除去する。]
[0105] そのため、ネットワークはコンテンツの分散を自己最適化する。一般に、少数のユーザにとって特に興味深いアイテムは、ユーザベースの記憶装置で保持される。ローカルサービス提供エリア内で一般に関心が持たれるアイテムは、ローカル記憶装置で保持される。そのため、一部のローカル記憶装置は、例えば、サービス対象の近隣エリアにおける民族性または話し言葉に基づき、他のローカル記憶装置とは相当異なる数組のアイテムを保持する。事前に予測できない特別のまたは稀に関心が寄せられるアイテムは、遠隔記憶装置で保持される。]
[0106] 例に戻って、「エバンオールマイティ」が第１ユーザ記憶装置１０２にローカル保存されていないとコンテンツ配信ネットワーク１００が判断すると仮定する。次いでユーザは、第１ローカルネットワーク記憶装置１０６から、第２ユーザ記憶装置１０４のような、第１ローカルネットワーク記憶装置１０６と結びついた別のユーザから、または第１遠隔ネットワーク記憶装置１１０のような、より遠隔のキャッシングノードからコピーを取得することができる。]
[0107] コンテンツ配信ネットワーク１００はまず、サービスプロバイダの現地交換拠点に位置する第１ローカルネットワーク記憶装置１０６への通信リンク１２０を確認する。「エバンオールマイティ」がユーザにとって有益であるとの情報に基づき、コンテンツ配信ネットワーク１００はピーク外時間中にローカルキャッシュに「エバンオールマイティ」を追加することを試みる。こうしたピーク外時間は、ノード間で通信される容量情報に基づき特定される。]
[0108] 「エバンオールマイティ」は、当該ユーザにとどまらずより広く関心を持たれている場合、多くのユーザのキャッシュの容量を使用するのではなく、第１ローカルネットワーク記憶装置１０６に保持することができる。多くのローカルまたはユーザのノードがフィルムのコピーを欲しいと思った場合、ローカルネットワーク記憶装置１０６はマルチキャストまたはブロードキャストのモードで映画を送信することができ、それにより多くのノードで同時に当該コピーを入手することができる。]
[0109] 「エバンオールマイティ」のコピーがノードに保存されると、ノードが一杯になり、当該映画がより有益なコンテンツに取って代わられるまで、当該コピーはノードに保存される。そのときでも、新たなコンテンツは、関心のあるユーザの数、アクセス確率などに基づき「エバンオールマイティ」「より優れた」ものでなければならない。「より優れた」コンテンツによる場合を除きコンテンツの置換を回避するため、コンテンツ配信ネットワーク１００は、有用性が同程度のアイテムがスワップインおよびスワップアウトされるときに生じるチャーニングを最小限に抑える。]
[0110] 上記にしたがい、様々な例示的実施形態は、複数のネットワークレベルにおけるキャッシングの効率性を高め、需要のピークの負荷を軽減するために、将来のコンテンツ消費確率についての予測情報を使用する。そのため、様々な例示的実施形態は、コンテンツ配信ネットワークで独自コンテンツがユーザに配信され得る際の費用対効果を改善する。]
[0111] 様々な例示的実施形態について、その特定の例示的態様に特に言及して詳しく説明してきたが、本発明は他の異なる実施形態も可能であり、その詳細は様々な明白な点で変更可能であることを理解すべきである。当業者はすぐに理解できることだが、本発明の精神および範囲内にとどまりながらも変形および変更を行うことが可能である。したがって、前述の開示、説明および図は、例示のためのものにすぎず、本発明を一切限定せず、本発明は特許請求の範囲によってのみ定められる。]

权利要求:

請求項1
コンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法であって、現在キャッシュされているコンテンツアイテムのリストを第１ネットワークノードで特定することと、第１ネットワークノードに対し要求される可能性が最も高い１つまたは複数のコンテンツアイテムを示す、有用性の最も高いコンテンツアイテムのリストを作成することと、有用性の最も高いコンテンツアイテムのリストにあって、現在キャッシュされているコンテンツアイテムのリストにないアイテムを含む、キャッシング候補のリストを特定することと、キャッシング候補のリストによる選択済みコンテンツアイテムを第１ネットワークノードにおいて第２ネットワークノードから受信することとを含む、方法。
請求項2
コンテンツ配信ネットワークがユニキャスト、ブロードキャスト、交換ブロードキャストおよびマルチキャストのネットワークの１つである、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項3
現在キャッシュされているコンテンツアイテムのリストを特定するステップが、第１ネットワークノードが１つまたは複数のコンテンツアイテムのアクセス確率の変化を識別したときに始まる、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項4
キャッシング候補のリストが、コンテンツアイテムがアクセスされる確率を示す有用性の尺度にしたがい順位付けされる、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項5
選択済みコンテンツアイテムが、キャッシング候補のリストによる最高順位のコンテンツアイテムである、請求項４に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項6
選択済みコンテンツアイテムを記憶するには第１ネットワークノードの記憶容量が不十分なときに１つまたは複数のコンテンツアイテムを除外することをさらに含む、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項7
除外する１つまたは複数のコンテンツアイテムの全体的な有用性が、選択済みコンテンツアイテムの有用性を所定のしきい値だけ下回ったときのみ、１つまたは複数のコンテンツアイテムを除外するステップが発生する、請求項６に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項8
選択済みコンテンツアイテムを受信するステップがピーク外時間中にのみ発生する、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項9
第２ネットワークノードに現在記憶されているコンテンツアイテムに関する情報を提供するアップデートを、第２ネットワークノードから第１ネットワークノードに送信することをさらに含む、請求項１に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項10
第２ネットワークノードに現在記憶されている全コンテンツアイテムをアップデートがリストアップする、請求項９に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項11
第１ネットワークノードに対する前回アップデート以降の第２ネットワークノードにおける除外アイテムおよび記憶された追加アイテムのみをアップデートがリストアップする、請求項９に記載のコンテンツ配信ネットワークに記憶されたコンテンツアイテムを管理する方法。
請求項12
コンテンツ配信ネットワークにおけるコンテンツアイテムをキャッシュするネットワークノードであって、１つまたは複数のコンテンツアイテムを記憶する記憶部と、有用性の最も高いコンテンツアイテムのリストにあって、現在キャッシュされているコンテンツアイテムのリストにないアイテムを識別することによってキャッシング候補のリストを形成する監視部であって、有用性の最も高いコンテンツアイテムのリストが、要求される可能性が最も高い１つまたは複数のコンテンツアイテムを示す、監視部と、キャッシング候補のリストにおける選択済みコンテンツアイテムをサーバネットワークノードから受信する受信部とを備える、ネットワークノード。
請求項13
コンテンツ配信ネットワークがユニキャスト、ブロードキャスト、交換ブロードキャストおよびマルチキャストのネットワークの１つである、請求項１２に記載のコンテンツ配信ネットワークにおけるコンテンツアイテムをキャッシュするネットワークノード。
請求項14
選択済みコンテンツアイテムを記憶するには記憶部の記憶容量が不十分なときに１つまたは複数のコンテンツアイテムを記憶部が除外する、請求項１２に記載のコンテンツ配信ネットワークにおけるコンテンツアイテムをキャッシュするネットワークノード。
請求項15
コンテンツ配信ネットワークにおけるコンテンツアイテムを配信するネットワークノードであって、１つまたは複数のコンテンツアイテムを記憶する記憶部と、有用性の最も高いコンテンツアイテムのリストにあって、現在キャッシュされているコンテンツアイテムのリストにないアイテムを識別することによってダウンロード要求を形成するクライアントネットワークノードから、ダウンロード要求を受信する受信部であって、有用性の最も高いコンテンツアイテムのリストが、クライアントネットワークノードに対し要求される可能性が最も高い１つまたは複数のコンテンツアイテムを示す、受信部と、記憶部に記憶されている、ダウンロード要求によって識別された選択済みコンテンツアイテムをクライアントネットワークノードに送信する送信部とを備える、ネットワークノード。
請求項16
少なくとも１つの隣接ノードに対し、記憶部に記憶されたコンテンツのリストおよび到達可能な記憶ノードのリストを通信するアップデート部をさらに備える、請求項１５に記載のコンテンツ配信ネットワークにおけるコンテンツアイテムを配信するネットワークノード。
請求項17
選択済みコンテンツアイテムを記憶するにはクライアントネットワークノードの記憶容量が不十分なときに１つまたは複数のコンテンツアイテムをクライアントネットワークノードが除外する、請求項１５に記載のコンテンツ配信ネットワークにおけるコンテンツアイテムを配信するネットワークノード。
請求項18
コンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワークであって、現在キャッシュされているコンテンツアイテムのリストおよび有用性の最も高いコンテンツアイテムのリストを特定する第１ネットワークノードであって、有用性の最も高いコンテンツアイテムのリストが、第１ネットワークノードに対し要求される可能性の最も高い１つまたは複数のコンテンツアイテムを示す、第１ネットワークノードと、１つまたは複数のコンテンツアイテムを記憶する第２ネットワークノードとを備え、有用性の最も高いコンテンツアイテムのリストにあって、現在キャッシュされているコンテンツアイテムのリストにないアイテムを含むキャッシング候補のリストを第１ネットワークノードが特定し、キャッシング候補のリストにおける選択済みコンテンツアイテムを第１ネットワークノードが第２ネットワークノードから受信する、コンテンツ配信ネットワーク。
請求項19
コンテンツ配信ネットワークがユニキャスト、ブロードキャスト、交換ブロードキャストおよびマルチキャストのネットワークの１つである、請求項１８に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項20
第１ネットワークノードが１つまたは複数のコンテンツアイテムのアクセス確率の変化を識別したときに第１ネットワークノードが現在キャッシュされているコンテンツアイテムのリストを特定する、請求項１８に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項21
アクセス確率に基づく有用性によってキャッシング候補のリストが順位付けされる、請求項１８に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項22
選択済みコンテンツアイテムが、キャッシング候補のリストによる最高順位のコンテンツアイテムである、請求項２１に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項23
選択済みコンテンツアイテムを記憶するには第１ネットワークノードの記憶容量が不十分なときに１つまたは複数のコンテンツアイテムを第１ネットワークノードが除外する、請求項１８に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項24
除外する１つまたは複数のコンテンツアイテムの全体的な有用性が、選択済みコンテンツアイテムの有用性を所定のしきい値だけ下回ったときのみ、１つまたは複数のコンテンツアイテムを第１ネットワークノードが除外する、請求項２３に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。
請求項25
ピーク外時間中にのみ第１ネットワークノードが選択済みコンテンツアイテムを受信する、請求項１８に記載のコンテンツアイテムの記憶を動的に管理するコンテンツ配信ネットワーク。